Master Theorem Examples

Let’s understand examples related to the master theorem.. We’ll solve some examples from each case.

Examples#

The following are some examples of the master theorem. Let’s look at them one by one.

Example 1#

This is the case of merge sort. Its time complexity is T(n)T(n) = 2T(n/2)2 T(n/2) + nn.

Solution

In this example, aa and bb are both equal to 2. So, logbalog_ba = log22log_22 = 1 which means that f(n)f(n) = n = Θ(nlog22.log0n)\Theta(n^{log_22}.log^0n). That means case 2 is applied and T(n)T(n) = Θ(nlog22.log0+1n)\Theta(n^{log_22}.log^{0+1}n). Its final time complexity is T(n)T(n) = Θ(n.log(n))\Theta(n.log(n)).

Example 2#

This is a case of binary search. Its time complexity is T(n)T(n) = T(n/2)T(n/2) + kk.

Solution

In this example, aa is equal to 1 and bb is equal to 2. So, logbalog_ba = log21log_21 = 0 which means that f(n)f(n) = k = Θ(nlog21.log0n)\Theta(n^{log_21}.log^0n). That means case 2 is applied and T(n)T(n) = Θ(nlog21.log0+1n)\Theta(n^{log_21}.log^{0+1}n). Its final time complexity is T(n)T(n) = Θ(log(n))\Theta(log(n)).

Example 3#

This is a case of binary tree traversal. Its time complexity is T(n)T(n) = 2T(n/2)T(n/2) + kk.

Solution

In this example, aa is equal to 2 and bb is also equal to 2. So, logbalog_ba = log22log_22 = 1 which means that f(n)f(n) = k = O(nlog221)O(n^{log_22-1}). That means case 1 is applied and T(n)T(n) = Θ(nlog22)\Theta(n^{log_22}). Its final time complexity is T(n)T(n) = Θ(n)\Theta(n).

Example 4#

In this example, an algorithm has a time complexity of T(n)T(n) = 2T(n/2)T(n/2) + n2n^2.

Solution

In this example, aa is equal to 2 and bb is also equal to 2. So, logbalog_ba = log22log_22 = 1 which means that f(n)f(n) = n2n^2 = Ω(nlog22+1)\Omega(n^{log_22+1}). That means case 3 is applied and T(n)T(n) = Θ(f(n))\Theta(f(n)). Its final time complexity is T(n)T(n) = Θ(n2)\Theta(n^2).

Let’s test what we’ve learned so far with a quick assessment.

Quick Assessment

Question

What is the time complexity of T(n)T(n) = 4T(n/2)T(n/2) + n2n^{2}?

Hide Answer

In this example, aa is equal to 4 and bb is equal to 2. So, logbalog_ba = log24log_24 = 2 which means that f(n)f(n) = n2n^2 = θ(nlog24.log0n)\theta(n^{log_24}.log^0n). That means case 2 is applied and T(n)T(n) = θ(nlog24.log0+1n)\theta(n^{log_24}.log^{0+1}n). Its final time complexity is T(n)T(n) = Θ(n2.log(n))\Theta(n^2.log(n)).

Example 5#

In this example, an algorithm has a time complexity of T(n)T(n) = T(n/2)T(n/2) + 2n2n.

Solution

In this example, aa is equal to 1 and bb is equal to 2. So, logbalog_ba = log21log_21 = 0 which means that f(n)f(n) = 2n2n = Ω(nlog21+1)\Omega(n^{log_21+1}). That means case 3 is applied. Its final time complexity is T(n)T(n) = Θ(n)\Theta(n).

Example 6#

In this example, an algorithm has a time complexity of T(n)T(n) = 16 T(n/4)T(n/4) + nn.

Solution

In this example, aa is equal to 16 and bb is equal to 4. So, logbalog_ba = log416log_416 = 2 which means that f(n)f(n) = nn = O(nlog4161)O(n^{log_416-1}). That means case 1 is applied. Its final time complexity is T(n)T(n) = Θ(n2)\Theta(n^2).

Example 7#

In this example, an algorithm has a time complexity of T(n)T(n) = 2 T(n/2)T(n/2) + nlog(n)nlog(n).

Solution

In this example, aa is equal to 2 and bb is equal to 2. So, logbalog_ba = log22log_22 = 1 which means that f(n)f(n) = nlog(n)nlog(n) = Θ(nlog22log1n)\Theta(n^{log_22}log^1n). That means case 2 is applied. Its final time complexity is T(n)T(n) = Θ(nlog22log1+1n)\Theta(n^{log_22}log^{1+1}n) = Θ(n.log2(n))\Theta(n.log^2(n)).

Example 8#

In this example, an algorithm has a time complexity of T(n)T(n) = 2 T(n/4)T(n/4) + n0.5n^{0.5} .

Solution

In this example, aa is equal to 2 and bb is equal to 4. So, logbalog_ba = log42log_42 = 0.5 which means that f(n)f(n) = n0.5n^{0.5} = Θ(nlog42log0n)\Theta(n^{log_42}log^0n). That means case 2 is applied. Its final time complexity is T(n)T(n) = Θ(nlog42log0+1n)\Theta(n^{log_42}log^{0+1}n) = Θ(n0.5.log(n))\Theta(n^{0.5}.log(n)).

Example 9#

In this example, an algorithm has a time complexity of T(n)T(n) = 3 T(n/3)T(n/3) + n√ n .

Solution

In this example, aa is equal to 3 and bb is also equal to 3. So, logbalog_ba = log33log_33 = 1 which means that case 1 is applied. Its final time complexity is T(n)T(n) = Θ(n)\Theta(n).

Example 10#

In this example, an algorithm has a time complexity of T(n)T(n) = 3 T(n/4)T(n/4) + nlog(n)nlog(n) .

Solution

In this example, aa is equal to 3 and bb is equal to 4. So, logba=log43=0.79log_ba= log_43 = 0.79 which means that f(n)f(n) = nlog(n)nlog(n) = Ω(nlog43log1n)\Omega(n^{log_43}log^1n). By applying logarithmic rules we know that n > nlog43n^{log_43} or nlog44n^{log_44} > nlog43n^{log_43} or log(4)log(4) > log(3)log(3) Case 3 is applied . Its final time complexity will be T(n)T(n) = Θ(n.log(n))\Theta(n.log(n)).

Master Theorem

Quiz